#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int value;
	struct node *next;
}NODE;

//Append the element to the list and return the new HEAD 
NODE * append_to_list (NODE *head, int x)
{
	NODE *temp;

	temp = malloc(sizeof(NODE));
	temp->value = x;
	temp->next = head;

	NODE *active;

	if (!head)
		return temp;

	active = head;
	while (active->next && active->next != head)
		active = active->next;
	active->next = temp;

	return head;
}


//Print a linked list
void print_list (NODE *head)
{

	printf ("\n");
	while (head) {
		printf ("%d\t", head->value);
		head = head->next;
	}
	printf ("\n");
	return;
}


//Search for an element
NODE * search (NODE * head, int x)
{
	while (head) {
		if (head->value == x)
			return head;
		head = head->next;
	}
	return NULL;
}

//Delete an element
NODE * delete_node (NODE * head, int x)
{
	NODE *prev = NULL, *active;

	active = head;
	while (active) {
		if (active->value == x) {
			if (prev) {
				prev->next = active->next;
				free (active);
				return head;
			} else {
				free (head);
				return active->next;
			}
		}
		prev = active;
		active = active->next;
	}

	return NULL;
}


NODE *remove_duplicates (NODE *head)
{
	NODE *active, *iterator, *prev, *temp;

	active = head;

	while (active) {
		iterator = head;
		prev = NULL;
		while (iterator) {
			if (iterator->value == active->value) {
				if (iterator == active) {
					active = active->next;
					iterator = NULL;
				} else {
					prev->next = iterator->next;
					temp = iterator;
					iterator = iterator->next;
					free (temp);
				}
			} else {
				prev = iterator;
				iterator = iterator->next;
			}
		}

	}

	return head;
}

void print_nth_element_from_last (NODE *head, int n)
{
	NODE *p1;
	NODE *p2;
	int i;

	p1 = p2 = head;

	for (i=0; i < n; i++) {
		if (!p2->next) {
			if (i==n-1) 
				printf ("The needed element: %d\n", p1->value);
			else 
				printf ("List too small for finding %d th/st/rd/nd element from last.%d\n", n, i);
			return;
		} 
		p2 = p2->next;
	}

	while (p2->next) {
		p1 = p1->next;
		p2 = p2->next;
	}

	printf ("The needed element: %d\n", p1->next->value);
}

NODE * detect_loop (NODE * head)
{
	NODE *p1;
	NODE *p2;
	p1 = p2 = head;

	do {
		p1 = p1->next;
		p2 = p2->next;
		if (p2 && p2->next) 
			p2 = p2->next;
		else {
			printf ("Not looping list\n");
			return NULL;
		}

	} while (p1 != p2);

	printf ("Circular list\n");

	p1 = head;
	while (p1 != p2) {
		p1 = p1->next;
		p2 = p2->next;
	}

	printf ("Loop happening at: %d\n", p2->value);

	return NULL;
}

int main()
{
	NODE *head;

	head = append_to_list (NULL, 1);
	head = append_to_list (head, 2);
	head = append_to_list (head, 3);
	head = append_to_list (head, 4);
	head = append_to_list (head, 5);

	NODE *temp1, *temp2;
	temp1 = search (head, 1);
	temp2 = search (head, 5);

	temp2->next = temp1;

	//print_list (head);

	detect_loop (head);

	return 0;
}
